This invention relates to a pattern string matching apparatus and a pattern string matching method for use in a character recognition apparatus. The apparatus and method is designed to effect matching process for matching, for example, a first character string which has been recognized by character recognition and are to be matched, and candidates of a second character string, which is registered in a database.
Hitherto, a pattern matching process is performed, as an important process, in a character recognition apparatus in order to obtain the results of character recognition. The pattern matching process achieves matching (comparison) between candidates of a first character string which has been recognized by character recognition and are to be matched and candidates of a second character string, which is stored in a database (dictionary). Thus, the pattern matching process accomplishes the best matching between a string of characters obtained by character recognition and one of the strings of characters, registered in the database.
When the pattern string matching process is effected, various combinations of candidates of the first character string are provided according to character candidates obtained by character recognition. Further, a large number of candidates of the second character string which are matched with the first character string are provided.
As the conventional pattern string matching process, a DP matching method, a matching process by a voting method and the like are provided.
In the DP matching method, a pass searching process is effected for a plurality of character candidates constructing the first character string. However, in the DP matching method, if the candidates of recognized characters of the first character string are increased in an order of first, second, third . . . , a searching space is exponentially increased and the processing speed is extremely lowered.
Further, the matching process performed by the voting method is to vote for candidates of the second character string sequentially, by comparing each candidate of the second character string with the first character string, character by character, and then to select the candidate of the second string, which has the largest voted score. However, in this method, the character arrangement of the character string is not taken into consideration. Therefore, in a case where characters constructing the first character strings are the same but the character arrangements thereof are different, the character strings cannot be distinguished from each other. Particularly, in cultural areas using alphabetic characters, since the number of types of letters is as small as 26, the above problem becomes significant.
Therefore, it is the most important subject of the pattern string matching process how to efficiently and correctly effect the matching process for a plurality of candidates of a character string and a plurality of candidates of a character string. That is, it is required to develop a pattern string matching process for effecting the matching process at “high speed” with “the character arrangement taken into consideration”.
Further, in the pattern string matching process, noise becomes a problem. For example, suppose a case wherein cut-out of the character fails and a character different from the word is contained in the first character string in the process for recognizing the characters constructing the first character string. In this case, even if a correct character string is contained in the first character string, it becomes impossible to match them by use of the conventional method such as the DP matching method in many cases.
If the voting method is used, it is difficult to get information on a matched portion after the matching process and it is difficult to remove the noise and separately recognize the character.
Thus, the matching process which is highly “noise-resistant” and can “specify the noise position” with high precision is required.